#include <time.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
static int point = 0;

struct PCB
{
    int pid;      // 进程ID
    int priority; // 进程优先级
    int time;     // 进程运行时间
    PCB *next;    // 指向下一个进程的指针
};
// 使用尾插法创建一个PCB链表
void tailCreate(PCB *L)
{
    srand((unsigned int)time(0)); // 使用当前时间作为随机种子
    int priority = rand() % 5;    // 随机生成一个优先级基值
    PCB *s, *r = L;               // s用于新建节点，r指向当前链表的尾部
    for (int i = 0; i < 5; i++)
    {
        int number = rand() % 5; // 随机生成运行时间
        while (number == 0)      // 确保运行时间不为0
            number = rand() % 5;

        s = new PCB;                          // 分配新节点
        s->pid = i + 1;                       // 设置进程ID
        s->priority = (i + priority) % 5 + 1; // 设置优先级
        s->time = number;                     // 设置运行时间

        if (s->priority != 5 || r->next == NULL)
        {
            r->next = s; // 如果优先级不是5，直接插入尾部
            r = s;
        }
        if ((s->priority == 5) && (r->next != NULL))
        {
            s->next = L->next; // 如果优先级是5，将该节点插入链表头部
            L->next = s;
        }
    }
    r->next = NULL; // 确保链表以NULL结束
}

// 模拟运行PCB链表中的进程
void run(PCB *L)
{
    PCB *c = L; // 链表头节点
    PCB *p = L; // 遍历用指针
    for (L; L; L = L->next)
    {                        // 遍历链表
        if (L->next == NULL) // 如果下一个节点为空，结束循环
            break;

        // 更新下一个进程的优先级和运行时间
        L->next->priority = L->next->priority - 1;
        L->next->time = L->next->time - 1;

        if (L->next->time == 0)
        {                                                            // 如果运行时间为0
            cout << "run over" << "->PID->" << L->next->pid << endl; // 输出进程完成信息
            L->next->time = -1;                                      // 标记为已完成
            L->next = L->next->next;                                 // 从链表中移除该节点

            // 如果链表中还有其他未完成进程
            if (L->next != NULL && L->next->time != 0)
            {
                L->next->priority = L->next->priority - 1;
                L->next->time = L->next->time - 1;
            }

            // 检查连续完成的进程
            while (L->next != NULL && L->next->time == 0)
            {
                cout << "run over" << "->PID->" << L->next->pid << endl;
                L->next->time = -1;
                L->next = L->next->next;

                if (L->next != NULL)
                {
                    L->next->priority = L->next->priority - 1;
                    L->next->time = L->next->time - 1;
                }
            }
        }

        // 如果优先级为0，将该节点移到链表头部并重置优先级
        if (L->next != NULL && L->next->priority == 0)
        {
            PCB *q = L->next;
            L->next = L->next->next; // 从当前位置移除
            q->priority = 5;         // 重置优先级为5
            q->next = c->next;       // 插入到链表头部
            c->next = q;
        }

        L = p; // 返回到前一个节点，继续处理
    }
}

int main()
{
    PCB *L, *m;
    L = new PCB;
    L->next = NULL;
    tailCreate(L);
    m = L;
    L = L->next;
    cout << "Init" << endl;
    cout << "=============" << endl;

    for (L; L; L = L->next)
    {
        cout << "PID :" << L->pid << endl;
        cout << "Time :" << L->time << endl;
        cout << "Priority :" << L->priority << endl;
        cout << "-------------" << endl;
    }

    cout << "Init successful !" << endl;
    cout << "=============" << endl;
    cout << "run order" << endl;
    while (point != 5)
    {
        run(m);
    }
    system("pause");
    return 0;
}
